{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split the Array to Make Coprime Products"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findValidSplit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割数组使乘积互质"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，下标从 <strong>0</strong> 开始。</p>\n",
    "\n",
    "<p>如果在下标 <code>i</code> 处 <strong>分割</strong> 数组，其中 <code>0 &lt;= i &lt;= n - 2</code> ，使前 <code>i + 1</code> 个元素的乘积和剩余元素的乘积互质，则认为该分割 <strong>有效</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>nums = [2, 3, 3]</code> ，那么在下标 <code>i = 0</code> 处的分割有效，因为 <code>2</code> 和 <code>9</code> 互质，而在下标 <code>i = 1</code> 处的分割无效，因为 <code>6</code> 和 <code>3</code> 不互质。在下标 <code>i = 2</code> 处的分割也无效，因为 <code>i == n - 1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回可以有效分割数组的最小下标 <code>i</code> ，如果不存在有效分割，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>当且仅当 <code>gcd(val1, val2) == 1</code> 成立时，<code>val1</code> 和 <code>val2</code> 这两个值才是互质的，其中 <code>gcd(val1, val2)</code> 表示 <code>val1</code> 和 <code>val2</code> 的最大公约数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/14/second.PNG\" style=\"width: 450px; height: 211px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,7,8,15,3,5]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。\n",
    "唯一一个有效分割位于下标 2 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/14/capture.PNG\" style=\"width: 450px; height: 215px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,7,15,8,3,5]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。\n",
    "不存在有效分割。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-the-array-to-make-coprime-products](https://leetcode.cn/problems/split-the-array-to-make-coprime-products/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-the-array-to-make-coprime-products](https://leetcode.cn/problems/split-the-array-to-make-coprime-products/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,7,8,15,3,5]', '[4,7,15,8,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = defaultdict(int)\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors[i] += 1\n",
    "                    primes[i] += 1\n",
    "            if n > 1:\n",
    "                factors[n] += 1\n",
    "                primes[n] += 1\n",
    "            return factors\n",
    "\n",
    "\n",
    "        primes = defaultdict(int)\n",
    "        mem = {}\n",
    "\n",
    "        for num in nums:\n",
    "            p = mem.setdefault(num, prime_factors(num))\n",
    "            # for k in p:\n",
    "            #     primes[k] += p[k]\n",
    "\n",
    "        l = set()\n",
    "\n",
    "        for i, num in enumerate(nums[:-1]):\n",
    "            tmp = mem[num]\n",
    "            for k in tmp:\n",
    "                primes[k] -= tmp[k]\n",
    "                l.add(k)\n",
    "                if not primes[k]: l.remove(k)\n",
    "\n",
    "            if not l:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        l=0\n",
    "        for i in range(n-1):\n",
    "            for j in range(l+1,n):\n",
    "                if gcd(nums[i],nums[j])!=1:\n",
    "                    l=j\n",
    "            if l==i:return l\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        idx=0\n",
    "        left=0\n",
    "        while left<=idx:\n",
    "            if idx==n-1:\n",
    "                return -1\n",
    "            for right in range(idx+1,n):\n",
    "                if math.gcd(nums[left],nums[right])!=1:\n",
    "                    idx=right\n",
    "            left+=1\n",
    "        return idx\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}  # left[p] 表示质数 p 首次出现的下标\n",
    "        right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值\n",
    "\n",
    "        def f(p: int, i: int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值\n",
    "            else:\n",
    "                left[p] = i  # 第一次遇到质数 p\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "\n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:  # 最远可以遇到 max_r\n",
    "                return max_r  # 也可以写 l-1\n",
    "            max_r = max(max_r, r)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}  # left[p] 表示质数 p 首次出现的下标\n",
    "        right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值\n",
    "\n",
    "        def f(p: int, i: int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值\n",
    "            else:\n",
    "                left[p] = i  # 第一次遇到质数 p\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "\n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:  # 最远可以遇到 max_r\n",
    "                return max_r  # 也可以写 l-1\n",
    "            max_r = max(max_r, r)\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}  # left[p] 表示质数 p 首次出现的下标\n",
    "        right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值\n",
    "\n",
    "        def f(p: int, i: int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值\n",
    "            else:\n",
    "                left[p] = i  # 第一次遇到质数 p\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:  # 最远可以遇到 max_r\n",
    "                return max_r  # 也可以写 l-1\n",
    "            max_r = max(max_r, r)\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {} \n",
    "        right = [0] * len(nums) \n",
    "\n",
    "        def f(p: int, i: int) -> None : \n",
    "            if p in left : \n",
    "                right[left[p]] = i \n",
    "            else : \n",
    "                left[p] = i \n",
    "        \n",
    "        for i, x in enumerate(nums) : \n",
    "            d = 2 \n",
    "            while d * d <= x : \n",
    "                if x % d == 0 : \n",
    "                    f(d, i) \n",
    "                    x //= d \n",
    "                    while x % d == 0 : \n",
    "                        x //= d \n",
    "                d += 1 \n",
    "            if x > 1 : f(x, i) \n",
    "        \n",
    "        max_r = 0 \n",
    "        for l, r in enumerate(right) : \n",
    "            if l > max_r : \n",
    "                return max_r \n",
    "            max_r = max(max_r, r) \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        def f(x, i):\n",
    "            if x not in left:\n",
    "                left[x] = i\n",
    "            else:\n",
    "                right[left[x]] = i\n",
    "\n",
    "        left = dict()\n",
    "        right = [0] * len(nums)\n",
    "\n",
    "        for i, v in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= v:\n",
    "                if not v % d:\n",
    "                    f(d, i)\n",
    "                    while not v % d:\n",
    "                        v //= d\n",
    "                d += 1\n",
    "            if v > 1:\n",
    "                f(v, i)\n",
    "\n",
    "        mr = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > mr:\n",
    "                return mr\n",
    "            mr = max(mr, r)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}\n",
    "        right = [0] * len(nums)\n",
    "\n",
    "        def f(p : int, i : int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i\n",
    "            else:\n",
    "                left[p] = i\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "        \n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:\n",
    "                return max_r\n",
    "            max_r = max(max_r, r)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}  # left[p] 表示质数 p 首次出现的下标\n",
    "        right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值\n",
    "\n",
    "        def f(p: int, i: int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值\n",
    "            else:\n",
    "                left[p] = i  # 第一次遇到质数 p\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "\n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:  # 最远可以遇到 max_r\n",
    "                return max_r  # 也可以写 l-1\n",
    "            max_r = max(max_r, r)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}  # left[p] 表示质数 p 首次出现的下标\n",
    "        right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值\n",
    "\n",
    "        def f(p: int, i: int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值\n",
    "            else:\n",
    "                left[p] = i  # 第一次遇到质数 p\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "\n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:  # 最远可以遇到 max_r\n",
    "                return max_r  # 也可以写 l-1\n",
    "            max_r = max(max_r, r)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        def fact(x):\n",
    "            ans = []\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    ans.append(d)\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: ans.append(x)\n",
    "            return ans\n",
    "        \n",
    "        n = len(nums)\n",
    "        pos = [i for i in range(n)]\n",
    "        vis = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            f = fact(x)\n",
    "            mn = inf\n",
    "            for y in f:\n",
    "                if y in vis:\n",
    "                    mn = min(mn, vis[y])\n",
    "                else:\n",
    "                    vis[y] = i\n",
    "            if mn != inf:\n",
    "                pos[i] = mn\n",
    "        ans = -1\n",
    "        mn = n\n",
    "        for i in range(n-1, 0, -1):\n",
    "            mn = min(mn, pos[i])\n",
    "            if mn >= i:\n",
    "                ans = i-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        def p(x, i):\n",
    "            if x in left:\n",
    "                right[left[x]] = i\n",
    "            else:\n",
    "                left[x] = i\n",
    "        n = len(nums)\n",
    "        left = {}\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            j = 2\n",
    "            while j * j <= x:\n",
    "                if x % j == 0:\n",
    "                    p(j, i)\n",
    "                while x % j == 0:\n",
    "                    x //= j\n",
    "                j += 1\n",
    "            if x > 1: p(x, i)\n",
    "        mx = 0\n",
    "        # print(f'{right}')\n",
    "        for l, r in enumerate(right):\n",
    "            if l > mx:\n",
    "                return mx\n",
    "            mx = max(mx, r)\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left = {}  # left[p] 表示质数 p 首次出现的下标\n",
    "        right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值\n",
    "\n",
    "        def f(p: int, i: int) -> None:\n",
    "            if p in left:\n",
    "                right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值\n",
    "            else:\n",
    "                left[p] = i  # 第一次遇到质数 p\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: f(x, i)\n",
    "\n",
    "        max_r = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > max_r:  # 最远可以遇到 max_r\n",
    "                return max_r  # 也可以写 l-1\n",
    "            max_r = max(max_r, r)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        def p(x, i):\n",
    "            if x in left:\n",
    "                right[left[x]] = i\n",
    "            else:\n",
    "                left[x] = i\n",
    "        n = len(nums)\n",
    "        left = {}\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            j = 2\n",
    "            while j * j <= x:\n",
    "                if x % j == 0:\n",
    "                    p(j, i)\n",
    "                while x % j == 0:\n",
    "                    x //= j\n",
    "                j += 1\n",
    "            if x > 1: p(x, i)\n",
    "        mx = 0\n",
    "        print(f'{right}')\n",
    "        for l, r in enumerate(right):\n",
    "            if l > mx:\n",
    "                return mx\n",
    "            mx = max(mx, r)\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = {}\n",
    "        right = [0] * n \n",
    "        for i, num in enumerate(nums):\n",
    "            p = 2 \n",
    "            while p * p <= num:\n",
    "                if num % p == 0:\n",
    "                    if p not in left:\n",
    "                        left[p] = i \n",
    "                    else:\n",
    "                        right[left[p]] = max(right[left[p]], i)\n",
    "                    while num % p == 0:\n",
    "                        num //= p\n",
    "                p += 1 \n",
    "            if num > 1:\n",
    "                if num not in left:\n",
    "                    left[num] = i \n",
    "                else:\n",
    "                    right[left[num]] = max(right[left[num]], i)\n",
    "        # print(right)\n",
    "        rightMax = 0\n",
    "        for i in range(n):\n",
    "            if i > rightMax:\n",
    "                return rightMax \n",
    "            rightMax = max(rightMax, right[i])\n",
    "        return - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        def fact(x):\n",
    "            ans = []\n",
    "            d = 2\n",
    "            while d * d <= x:  # 分解质因数\n",
    "                if x % d == 0:\n",
    "                    ans.append(d)\n",
    "                    while x % d == 0:\n",
    "                        x //= d\n",
    "                d += 1\n",
    "            if x > 1: ans.append(x)\n",
    "            return ans\n",
    "        \n",
    "        n = len(nums)\n",
    "        pos = [i for i in range(n)] # 当前元素 x 的所有质因数中最早出现的位置\n",
    "        vis = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            f = fact(x) # 分解质因数\n",
    "            mn = inf\n",
    "            for y in f:\n",
    "                if y in vis: # 如果质因数出现过，比较最早出现的位置\n",
    "                    mn = min(mn, vis[y])\n",
    "                else:\n",
    "                    vis[y] = i # 质因数没有出现过，则当前位置为该质因数最早出现的位置\n",
    "            if mn != inf:\n",
    "                pos[i] = mn\n",
    "        ans = -1\n",
    "        mn = n\n",
    "        for i in range(n-1, 0, -1):\n",
    "            mn = min(mn, pos[i])\n",
    "            if mn >= i: # 如果当前元素所有质因数出现的位置都没有早于当前位置，则可以从当前位置的前一个元素开始划分\n",
    "                ans = i-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = Counter()\n",
    "        right = [0] * n \n",
    "        def f(x, i):\n",
    "            if x not in left:\n",
    "                left[x] = i \n",
    "            else:\n",
    "                right[left[x]] = i \n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            d = 2\n",
    "            while d * d <= x:\n",
    "                if x % d == 0:\n",
    "                    f(d, i)\n",
    "                    x //= d \n",
    "                    while x % d == 0:\n",
    "                        x //= d \n",
    "                d += 1\n",
    "            if x > 1:\n",
    "                f(x, i)\n",
    "        ans = 0\n",
    "        for l, r in enumerate(right):\n",
    "            if l > ans:\n",
    "                return ans\n",
    "            ans = max(ans, r)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left ={}\n",
    "        right=[0]*len(nums)\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            d =2\n",
    "            while d *d <=x:\n",
    "                if x%d == 0:\n",
    "                    if d in left:\n",
    "                        right[left[d]]=i\n",
    "                    else:\n",
    "                        left[d]=i\n",
    "                    x//=d\n",
    "                    while x%d==0:\n",
    "                        x//=d\n",
    "                d+=1\n",
    "            if x>1:\n",
    "                if x in left:\n",
    "                    right[left[x]]=i\n",
    "                else:\n",
    "                    left[x]=i\n",
    "        \n",
    "        max_r = 0\n",
    "\n",
    "        for l,r in enumerate(right):\n",
    "            if l> max_r:\n",
    "                return max_r\n",
    "            max_r = max(max_r,r)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        N = int(1e3) + 1\n",
    "        isPrime = [1] * N\n",
    "        primes = []\n",
    "        for i in range(2, N):\n",
    "            if isPrime[i]:\n",
    "                primes.append(i)\n",
    "            for j in range(len(primes)):\n",
    "                if i * primes[j] >= N:\n",
    "                    break \n",
    "                isPrime[i * primes[j]] = 0\n",
    "                if i % primes[j] == 0:\n",
    "                    break \n",
    "\n",
    "        lines = {p: [n, -1] for p in primes}\n",
    "        for i in range(n):\n",
    "            for p in primes:\n",
    "                if p * p > nums[i]:\n",
    "                    break \n",
    "                if nums[i] % p == 0:\n",
    "                    while nums[i] % p == 0:\n",
    "                        nums[i] //= p\n",
    "                    lines[p][0] = min(lines[p][0], i) \n",
    "                    lines[p][1] = max(lines[p][1], i) \n",
    "            if nums[i] > 1:\n",
    "                if nums[i] not in lines:\n",
    "                    lines[nums[i]] = [n, -1]\n",
    "                lines[nums[i]][0] = min(lines[nums[i]][0], i)\n",
    "                lines[nums[i]][1] = max(lines[nums[i]][1], i)\n",
    "\n",
    "        arr = []\n",
    "        for k, val in lines.items():\n",
    "            arr.append(val)\n",
    "        arr.sort() \n",
    "        m = len(arr)\n",
    "        end = 0\n",
    "        j = 0\n",
    "        for i in range(n-1):\n",
    "            while j < m and i >= arr[j][0]:\n",
    "                end = max(end, arr[j][1])\n",
    "                j += 1\n",
    "            if i >= end:\n",
    "                return i \n",
    "        \n",
    "        return -1 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        prime = [2]\n",
    "        for i in range(3, int(sqrt(max(nums))) + 1):\n",
    "            isPrime = 1\n",
    "            for x in prime:\n",
    "                if x ** 2 > i:\n",
    "                    break\n",
    "                if i % x == 0:\n",
    "                    isPrime = 0\n",
    "                    break\n",
    "            if isPrime:\n",
    "                prime.append(i)\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            for x in prime:\n",
    "                if x ** 2 > nums[i]:\n",
    "                    break\n",
    "                if nums[i] % x == 0:\n",
    "                    dic.setdefault(x, []).append(i)\n",
    "                    while nums[i] % x == 0:\n",
    "                        nums[i] //= x\n",
    "            if nums[i] != 1:\n",
    "                dic.setdefault(nums[i], []).append(i)\n",
    "        intervals = []\n",
    "        for x in dic:\n",
    "            if len(dic[x]) > 1:\n",
    "                intervals.append([dic[x][0], dic[x][-1]])\n",
    "        intervals.sort(reverse = True)\n",
    "        for i in range(len(nums) - 1):\n",
    "            while intervals and intervals[-1][1] <= i:\n",
    "                intervals.pop()\n",
    "            if not intervals or intervals[-1][0] > i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**3\n",
    "isprime = [True] * (MX + 1)\n",
    "primes = []\n",
    "for num in range(2, MX + 1):\n",
    "    if isprime[num]:\n",
    "        primes.append(num)\n",
    "    for p in primes:\n",
    "        if num * p > MX:\n",
    "            break\n",
    "        isprime[num * p] = False\n",
    "        if num % p == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        last = defaultdict(int)\n",
    "        factors = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(nums):\n",
    "            for p in primes:\n",
    "                if x == 1:\n",
    "                    break\n",
    "                if x % p == 0:\n",
    "                    last[p] = i\n",
    "                    factors[i].append(p)\n",
    "                    while x % p == 0:\n",
    "                        x //= p\n",
    "            if x > 1:\n",
    "                last[x] = i\n",
    "                factors[i].append(x)\n",
    "        \n",
    "        rightmost = 0\n",
    "        for i, fs in enumerate(factors[:-1]):\n",
    "            valid = i == rightmost\n",
    "            for p in fs:\n",
    "                if last[p] > rightmost:\n",
    "                    valid = False\n",
    "                    rightmost = last[p]\n",
    "            if valid:\n",
    "                return i\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def primeSplit(self, number, primes, location):\n",
    "        factors = [i for i in range(1, int(math.sqrt(number)) + 2) if number % i == 0]\n",
    "        for i in range(len(factors)):\n",
    "            if number % factors[i] == 0 and factors[i] < number // factors[i]:\n",
    "                factors.append(number // factors[i])\n",
    "        factors = sorted(factors)[1:]\n",
    "        for factor in factors:\n",
    "            if number % factor != 0: continue\n",
    "            if factor in primes:\n",
    "                ranges = primes[factor]\n",
    "                primes[factor] = [min(ranges[0], location), max(ranges[0], location)]\n",
    "            else: primes[factor] = [location, location]\n",
    "            while number % factor == 0:\n",
    "                number = number // factor\n",
    "\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        primes = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            self.primeSplit(x, primes, i)\n",
    "        ranges = sorted([x for x in primes.values()], key = lambda x: x[0])\n",
    "        result = 0\n",
    "        for i in range(len(ranges)):\n",
    "            if ranges[i][0] > result: break\n",
    "            result = max(result, ranges[i][1])\n",
    "        return result if result <= len(nums) - 2 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        start = defaultdict(int)\n",
    "        end = defaultdict(int)\n",
    "        for i, e in enumerate(nums):\n",
    "            for now in range(2, int(sqrt(e))+1):\n",
    "                if not e % now:\n",
    "                    if not start[now]:\n",
    "                        start[now] = i+1\n",
    "                    end[now] = i+1\n",
    "                    if not start[e//now]:\n",
    "                        start[e//now] = i+1\n",
    "                    end[e//now] = i+1\n",
    "            if e != 1:\n",
    "                if not start[e]:\n",
    "                    start[e] = i+1\n",
    "                end[e] = i+1\n",
    "        sorted_list = []\n",
    "        for k in start.keys():\n",
    "            insort(sorted_list, (start[k], end[k]))\n",
    "        right = 1\n",
    "        for l, r in sorted_list:\n",
    "            if l > right:\n",
    "                return right-1\n",
    "            else:\n",
    "                right = max(right, r)\n",
    "        return -1 if right == len(nums) else right-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**6\n",
    "minp = [0] * (MX + 1)\n",
    "primes = []\n",
    "for x in range(2, MX + 1):\n",
    "    if minp[x] == 0:\n",
    "        minp[x] = x\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if x * p > MX:\n",
    "            break\n",
    "        minp[x * p] = p\n",
    "        if p == minp[x]:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        last = defaultdict(int)\n",
    "        factors = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = minp[x]\n",
    "                last[p] = i\n",
    "                factors[i].append(p)\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "        \n",
    "        rightmost = 0\n",
    "        for i, fs in enumerate(factors[:-1]):\n",
    "            valid = i == rightmost\n",
    "            for p in fs:\n",
    "                if last[p] > rightmost:\n",
    "                    valid = False\n",
    "                    rightmost = last[p]\n",
    "            if valid:\n",
    "                return i\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6\n",
    "isPrime = [True] * (N + 1)\n",
    "Prime = []\n",
    "for i in range(2, N + 1):\n",
    "    if isPrime[i]:\n",
    "        Prime.append(i)\n",
    "    for p in Prime:\n",
    "        if i * p > N:\n",
    "            break\n",
    "        isPrime[i * p] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        def myprime(n):\n",
    "            ans = set()\n",
    "            for p in Prime:\n",
    "                if p * p > n:\n",
    "                    break\n",
    "                if n % p == 0:\n",
    "                    ans.add(p)\n",
    "                    while n % p == 0:\n",
    "                        n //= p\n",
    "            if n > 1:\n",
    "                ans.add(n)\n",
    "            return ans\n",
    "        n = len(nums)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        sl, sr = set(), set()\n",
    "        for i in range(n):\n",
    "            for j in myprime(nums[i]):\n",
    "                sl.add(j)\n",
    "            for j in myprime(nums[-1 - i]):\n",
    "                sr.add(j)\n",
    "            left[i] = len(sl)\n",
    "            right[-i - 1] = len(sr)\n",
    "        for i in range(n - 1):\n",
    "            if left[i] + right[i + 1] == left[-1]:\n",
    "                return i\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        print(len(nums))\n",
    "        n = max(nums) + 1\n",
    "        flag = [0] * n\n",
    "        primes = [2]\n",
    "        pos = dict()\n",
    "        pos[2] = 0\n",
    "        for i in range(3, n, 2):\n",
    "            if not flag[i]:\n",
    "                pos[i] = len(primes)\n",
    "                primes.append(i)\n",
    "                for j in range(i * i, n, i):\n",
    "                    flag[j] = 1\n",
    "        \n",
    "        n = len(primes)\n",
    "        left = [-1] * n\n",
    "        right = [-1] * n\n",
    "        for i in range(len(nums)):\n",
    "            x = nums[i]\n",
    "            for j in range(n):\n",
    "                p = primes[j]\n",
    "                if p * p > x:\n",
    "                    break\n",
    "                if x % p == 0:\n",
    "                    if left[j] == -1:\n",
    "                        left[j] = i\n",
    "                    right[j] = i\n",
    "                    while x % p == 0:\n",
    "                        x //= p\n",
    "            if x != 1:\n",
    "                j = pos[x]\n",
    "                if left[j] == -1:\n",
    "                    left[j] = i\n",
    "                right[j] = i\n",
    "        idx = [i for i in range(n) if left[i] != right[i]]\n",
    "        idx.sort(key=lambda i:left[i])\n",
    "        end = 0\n",
    "        for i in idx:\n",
    "            l, r = left[i] - 1, right[i]\n",
    "            # print(primes[i], l, r)\n",
    "            if l >= end:\n",
    "                return end\n",
    "            end = max(end, r)\n",
    "        if end < len(nums) - 1:\n",
    "            return end\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "ma = 10**6\n",
    "\n",
    "def get_primes(M):\n",
    "    f = [1]*M\n",
    "    for i in range(2,isqrt(M)+1):\n",
    "        if f[i]:\n",
    "            f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)\n",
    "    return [i for i in range(2,M) if f[i]]\n",
    "\n",
    "primes = get_primes(isqrt(ma)+1)\n",
    "\n",
    "@lru_cache(None)\n",
    "def factor(num):\n",
    "    cnts = Counter()\n",
    "    for x in primes:\n",
    "        if num % x == 0:\n",
    "            num //= x\n",
    "            cnts[x] += 1\n",
    "    if num > 1:\n",
    "        cnts[num] += 1\n",
    "    return cnts\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        \n",
    "        hashmap = defaultdict(int)\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            for x in factor(num):\n",
    "                hashmap[x] = i\n",
    "        \n",
    "        r = 0\n",
    "        for i , num in enumerate(nums[:-1]):\n",
    "            for x in factor(num):\n",
    "                r = max(r,hashmap[x])\n",
    "            if r == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        N = int(1e6)\n",
    "        mx = [-1] * N \n",
    "        mn = [float('inf')] * N \n",
    "        for i, x in enumerate(nums):\n",
    "            for p in range(2, int(math.sqrt(x)) + 2):\n",
    "                if x % p == 0:\n",
    "                    mx[p] = max(mx[p], i)\n",
    "                    mn[p] = min(mn[p], i)\n",
    "                    while x % p == 0:\n",
    "                        x //= p \n",
    "            if x > 1:\n",
    "                mx[x] = max(mx[x], i)\n",
    "                mn[x] = min(mn[x], i)\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        for x in range(N):\n",
    "            if mn[x] < mx[x]:\n",
    "                f[mn[x]] += 1\n",
    "                f[mx[x]] -= 1\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            ans += f[i] \n",
    "            if ans == 0:\n",
    "                return i \n",
    "        return -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "pt=PrimeTable(10**6+5)\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left=Counter()\n",
    "        right=Counter()\n",
    "        for x in nums:\n",
    "            for p,c in pt.prime_factorization(x):\n",
    "                right[p]+=c\n",
    "        for i,x in enumerate(nums[:-1]):\n",
    "            for p,c in pt.prime_factorization(x):\n",
    "                right[p]-=c\n",
    "                left[p]+=c\n",
    "            if all(right[p]==0 for p in left.keys()):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**6 + 1\n",
    "g = [[] for _ in range(N)]\n",
    "for i in range(2, N):\n",
    "    if g[i]: continue\n",
    "    for j in range(i, N, i):\n",
    "        g[j].append(i)\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = {}\n",
    "        for i,v in enumerate(nums):\n",
    "            for j in g[v]:\n",
    "                right[j] = i\n",
    "        i2 = 0\n",
    "        for i in range(n-1):\n",
    "            k = max((right[j] for j in g[nums[i]]), default=i)\n",
    "            i2 = max(i2, k)\n",
    "            if i == i2 or i2 == n-1:\n",
    "                break\n",
    "        return i if i == i2 < n-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXX=10**6\n",
    "fac=[[] for _ in range(MAXX+1)]\n",
    "for i in range(2,MAXX+1):\n",
    "    if len(fac[i])==0:\n",
    "        for j in range(i,MAXX+1,i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        left={} #left[p]种存储了质数p首次出现的下标\n",
    "        right=[0]*len(nums) #right[i]代表左端点为i的区间右端点的最大值\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            for p in fac[x]:\n",
    "                if p in left:\n",
    "                    right[left[p]]=i\n",
    "                else:\n",
    "                    left[p]=i\n",
    "        \n",
    "        max_r=0\n",
    "        for l,r in enumerate(right):\n",
    "            if l>max_r:\n",
    "                return max_r\n",
    "            max_r=max(max_r,r)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**6 + 1\n",
    "f = [[] for _ in range(N)]\n",
    "for i in range(2, N):\n",
    "    if f[i]: continue\n",
    "    for j in range(i, N, i):\n",
    "        f[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        c = Counter()\n",
    "        for x in nums:\n",
    "            for p in f[x]:\n",
    "                c[p] += 1\n",
    "        n = len(nums)\n",
    "        c1, cnt = Counter(), 0\n",
    "        for i,x in enumerate(nums):\n",
    "            if i == n-1:\n",
    "                return -1\n",
    "            for p in f[x]:\n",
    "                c1[p] += 1\n",
    "                if c1[p] == 1:\n",
    "                    cnt += 1\n",
    "                if c1[p] == c[p]:\n",
    "                    cnt -= 1\n",
    "            if cnt == 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**6 + 1\n",
    "f = [[] for _ in range(N)]\n",
    "for i in range(2, N):\n",
    "    if f[i]: continue\n",
    "    for j in range(i, N, i):\n",
    "        f[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def findValidSplit(self, nums: List[int]) -> int:\n",
    "        c = Counter()\n",
    "        for x in nums:\n",
    "            for p in f[x]:\n",
    "                c[p] += 1\n",
    "        n = len(nums)\n",
    "        c1, cnt = Counter(), 0\n",
    "        for i,x in enumerate(nums):\n",
    "            if i == n-1:\n",
    "                return -1\n",
    "            for p in f[x]:\n",
    "                c1[p] += 1\n",
    "                if c1[p] == 1:\n",
    "                    cnt += 1\n",
    "                if c1[p] == c[p]:\n",
    "                    cnt -= 1\n",
    "            if cnt == 0:\n",
    "                return i"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
